package class03

/*
	背包容量为w
	一共有 n 袋零食，低i袋零食体积为v[i] > 0
	总体等于背包容量的情况下，
	一共有多少种零食装法?
*/
func ways3(arr []int, w int) int {
	return process2(arr, 0, w)
}

func process2(arr []int, start, rest int) int {
	if start == len(arr) && rest != 0 {
		return -1
	} else if start == len(arr) && rest == 0 {
		return 1
	}
	var ans, p1, p2 int
	p1 = process2(arr, start+1, rest)
	p2 = process2(arr, start+1, rest-arr[start])
	if p1 != -1 {
		ans += p1
	}
	if p2 != -1 {
		ans += p2
	}
	return ans
}

func ways4(arr []int, w int) int {
	dp := make([][]int, len(arr)+1)
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, w+1)
	}
	for i:=1;i<=w; i++ {
		dp[len(arr)][i] = -1
	}
	dp[len(arr)][0] = 1

	for start:=len(arr)-1; start >=0; start-- {
		for rest:=w; rest>=0; rest-- {
			var cur int
			if dp[start+1][rest] != -1 {
				cur += dp[start+1][rest]
			}
			if rest-arr[start] >=0 && dp[start+1][rest-arr[start]] != -1 {
				cur += dp[start+1][rest-arr[start]]
			}
			dp[start][rest] = cur
		}
	}
	return dp[0][w]
}